using System;
using System.Collections;
using System.Threading;

public class SudokuMT
{
    static Random rand = new Random();
    static ulong MASK;
    static int N, N2, N3, N4, N2_1, N4_1, qn;
    static int version;

    static int[] rs;
    static Set[] sets;
    static Cell[] cells;
    static int[][] subs, pairs, pairsOfSubs;
    static ulong[] subsMask, pairsMask;
    static IQ subsIQ, pairsIQ, setsIQ;
    public int[] queryResults(int x, int[] qr)
    {
        cells[(qr[0] - 1) * N2 + qr[1] - 1].mask(1LU << (x - 1));
        if (qn < N2)
        {
            qr[1] = N * (qn % N) + (qn / N) + 1;
            qr[0] = ++qn;
            return qr;
        }
        double best = double.MinValue, tt;
        int bestk = -1, k;
        while (waitings != MTN - 1)
            Thread.Sleep(30);

        for (k = N4_1; k >= 0; k--)
            if (rs[k] == 0 && (tt = 3 * N * Count(cells[k].mk) + (k / N2) + (k % N2) + rand.NextDouble()) >= best)
            {
                best = tt; bestk = k;
            }
        if (bestk >= 0)
            return new int[] { (bestk / N2) + 1, (bestk % N2) + 1 };
        threading = false;
        return rs;
    }

    public int[] initialize(int n)
    {
        int i, j, k, l, s, e, a, b;
        qn = 1;
        N = n;
        N2 = n * n;
        N3 = N2 * n;
        N4 = N3 * n;
        N2_1 = N2 - 1;
        N4_1 = N4 - 1;
        MASK = 1LU << (N2_1);
        MASK = (MASK - 1) + MASK;

        rs = new int[N4];
        cells = new Cell[N4];
        for (i = N4_1; i >= 0; i--)
            cells[i] = new Cellsync(i);


        subsIQ = new IQsync(2 * N3);
        pairsIQ = new IQsync(4 * N3);
        setsIQ = new IQsync(3 * N2);

        subs = new int[2 * N3][];
        subsMask = new ulong[2 * N3];
        pairsOfSubs = new int[2 * N3][];
        for (i = subs.Length - 1; i >= 0; i--)
        {
            subs[i] = new int[n];
            subsMask[i] = MASK;
            pairsOfSubs[i] = new int[2 * (n - 1)];
        }
        pairs = new int[4 * N3][];
        pairsMask = new ulong[4 * N3];
        for (i = pairs.Length - 1; i >= 0; i--)
        {
            pairs[i] = new int[n - 1];
            pairsMask[i] = MASK;
        }

        sets = new Set[3 * N2];
        for (i = sets.Length - 1; i >= 0; i--)
            sets[i] = new SetSync(i);
        for (k = N4_1; k >= 0; k--)
        {
            i = k / N2;
            j = k % N2;
            sets[i].list[j] = cells[k].r;
            sets[N2 + j].list[i] = cells[k].c;
            sets[N2 + N2 + i / n * n + j / n].list[(i % n) * n + (j % n)] = cells[k].a;
            cells[k].s1 = a = i * n + j / n;
            cells[k].s2 = b = N3 + j * n + i / n;
            subs[a][j % n] = k;
            subs[b][i % n] = k;
        }
        for (i = sets.Length - 1; i >= 0; i--)
            sets[i].init();

        int d = N3 << 1;
        int[] posp = new int[pairsOfSubs.Length];
        for (k = N3 - 1; k >= 0; k--)
        {
            i = k / n;
            j = k % n;
            a = k << 1;
            for (l = 0, s = i * n, e = s + n; s < e; s++)
                if (s != k)
                {
                    pairs[a][l] = s;
                    pairs[d + a][l] = b = N3 + s;
                    l++;
                    pairsOfSubs[s][posp[s]++] = a;
                    pairsOfSubs[b][posp[b]++] = d + a;
                }
            a++;
            for (l = 0, s = i / n * N2 + j, e = s + N2; s < e; s += n)
                if (s != k)
                {
                    pairs[a][l] = s;
                    pairs[d + a][l] = b = N3 + s;
                    l++;
                    pairsOfSubs[s][posp[s]++] = a;
                    pairsOfSubs[b][posp[b]++] = d + a;
                }
        }
        threading = true;
        waitings = 0;
        for (i = MTN - 1; i > 0; i--)
            new ThreadRun();
        return new int[] { 1, 1 };
    }

    static int Count(ulong m)
    {
        int ret = 0;
        while (m > 0)
        {
            ret++;
            m = (m - 1) & m;
        }
        return ret;
    }
    static int First(ulong m)
    {
        for (int q = 0; q < N2; q++)
            if ((m & (1LU << q)) != 0LU)
                return q;
        if (m == 0)
            throw new Exception();
        return -1;
    }

    class Cell
    {
        protected Cell()
        { }
        public Cell(int k)
        {
            this.k = k;
            this.mk = MASK;
            this.r = new Element(this);
            this.c = new Element(this);
            this.a = new Element(this);
        }
        public ulong mk;
        public int s1, s2, k;
        public Element r, c, a;
        public virtual void get(int x)
        {
            mk = 1LU << x;
            subsIQ.Add(s1);
            subsIQ.Add(s2);
            r.update(mk);
            c.update(mk);
            a.update(mk);
            rs[k] = x + 1;
            r.get(x);
            c.get(x);
            a.get(x);
        }
        public virtual bool mask(ulong m)
        {
            if (mk != (mk & m))
            {
                mk &= m;
                subsIQ.Add(s1);
                subsIQ.Add(s2);
                r.update(mk);
                c.update(mk);
                a.update(mk);
                if (((mk - 1) & mk) == 0)
                {
                    int x = First(mk);
                    rs[k] = x + 1;
                    r.get(x);
                    c.get(x);
                    a.get(x);
                }
                Interlocked.Increment(ref version);
                return true;
            }
            return false;
        }
    }
    class Cellsync : Cell
    {
        public Cellsync(int k)
        {
            this.k = k;
            this.mk = MASK;
            this.r = new ElementSync(this);
            this.c = new ElementSync(this);
            this.a = new ElementSync(this);
        }
        public override void get(int x)
        {
            lock(this)
                base.get(x);
        }
        public override bool mask(ulong m)
        {
            lock (this)
                return base.mask(m);
        }
    }
    class Element
    {
        public Element(Cell c)
        {
            cell = c;
        }
        public Element left, right;
        public Set owner;
        public Cell cell;
        public ulong mk;
        public ulong pmk;
        public int eid;
        public virtual void update(ulong m)
        {
            mk = m;
            setsIQ.Add(owner.sid);
            m ^= MASK;
            for (int i = 0; m != 0; m >>= 1, i++)
            {
                if ((m & 1LU) != 0)
                    owner.ps[i] &= pmk;
                //else
                //    owner.ps[i] |= ~pmk;
            }
        }
        public virtual void get(int x)
        {
            owner.get(x);
            left.right = right;
            right.left = left;
        }
    }
    class ElementSync : Element
    {
        public ElementSync(Cell c)
            :base(c){ }
        public override void get(int x)
        {
            lock (this) 
                base.get(x);
        }
        public override void update(ulong m)
        {
            lock(this)
                base.update(m);
        }
    }
    class Set
    {
        public Set(int sid)
        {
            this.sid = sid;
            this.head = new Element(null);
            this.list = new Element[N2];
            mk = MASK;
            ps = new ulong[N2];
            for (int i = N2_1; i >= 0; i--)
                ps[i] = MASK;
        }
        public virtual void get(int x)
        {
            mk ^= 1LU << x;
            ps[x] = 0LU;
        }
        public int sid;
        public ulong[] ps;
        public ulong mk;
        public Element head;
        public Element[] list;
        public void init()
        {
            head.right = list[0];
            list[0].owner = this;
            list[0].eid = 0;
            list[0].pmk = 1LU ^ MASK;
            list[0].left = head;
            list[0].right = list[1];
            for (int i = N2 - 2; i > 0; i--)
            {
                list[i].owner = this;
                list[i].eid = i;
                list[i].pmk = (1LU << i) ^ MASK;
                list[i].left = list[i - 1];
                list[i].right = list[i + 1];
            }
            list[N2_1].owner = this;
            list[N2_1].eid = N2_1;
            list[N2_1].pmk = (1LU << N2_1) ^ MASK;
            list[N2_1].left = list[N2 - 2];
            list[N2_1].right = head;
            head.left = list[N2_1];
        }
        public void check(ThreadRun tr)
        {
            int i;
            ulong[] sms = tr.sms;
            int[,] tb = tr.tb;
            int[, ,] tb3 = tr.tb3;
            int[] h1 = tr.h1, h2 = tr.h2, h3 = tr.h3;

        Loop:
            bool changed = false;
            #region 1i
            Element e = head.right, ee;
            ulong mkb = mk;
            while (e != head)
            {
                e.cell.mask(mk);
                if (mk != mkb)
                {
                    mkb = mk;
                    e = head.right;
                }
                else
                    e = e.right;
            }
            #endregion;
            #region 1x
            ulong m;
            for (i = 0, e = head.right; e != head; i++, e = e.right)
                sms[i + 1] = sms[i] | e.mk;
            m = 0UL;
            for (i--, e = head.left; e != head; i--, e = e.left)
            {
                if ((m | sms[i]) != mk)
                {
                    e.cell.get(First((m | sms[i]) ^ mk));
                    goto Loop;
                }
                m |= e.mk;
            }
            #endregion

            #region 2i
            int a1, a2, hi = 0, a;
            ulong mmm;
            for (e = head.right; e != head; e = e.right)
            {
                mmm = e.mk;
                m = (mmm - 1) & mmm;
                if (m == 0)
                    throw new Exception();
                if (((m - 1) & m) == 0)
                {
                    a1 = First(mmm);
                    a2 = First(m);
                    if ((a = tb[a1, a2]) > 0)
                    {
                        m = e.mk ^ MASK;
                        for (ee = head.right; ee.eid != a; ee = ee.right)
                        {
                            changed |= ee.cell.mask(m);
                            if (mk != mkb)
                                goto Clear2i;
                        }
                        for (ee = ee.right; ee != e; ee = ee.right)
                        {
                            changed |= ee.cell.mask(m);
                            if (mk != mkb)
                                goto Clear2i;
                        }
                        for (ee = ee.right; ee != head; ee = ee.right)
                        {
                            changed |= ee.cell.mask(m);
                            if (mk != mkb)
                                goto Clear2i;
                        }
                    }
                    else
                    {
                        tb[a1, a2] = e.eid;
                        h1[hi] = a1;
                        h2[hi] = a2;
                        hi++;
                    }
                }
            }
        Clear2i:
            while (--hi >= 0)
                tb[h1[hi], h2[hi]] = -1;
            if (changed)
                goto Loop;
            #endregion
            #region 2x
            ulong mm;
            hi = 0;
            for (i = 0; i < N2; i++)
                if (ps[i] != 0)
                {
                    m = ps[i];
                    mm = (m - 1) & m;
                    if (mm == 0)
                        throw new Exception();
                    if (((mm - 1) & m) == 0)
                    {
                        a1 = First(m);
                        a2 = First(mm);
                        if ((a = tb[a1, a2]) >= 0)
                        {
                            m = (1LU << a) | (1LU << i);
                            changed |= list[a1].cell.mask(m);
                            changed |= list[a2].cell.mask(m);
                        }
                        else
                        {
                            tb[a1, a2] = i;
                            h1[hi] = a1;
                            h2[hi] = a2;
                            hi++;
                        }
                    }
                }
            while (--hi >= 0)
                tb[h1[hi], h2[hi]] = -1;
            if (changed)
                goto Loop;
            #endregion

            #region 3i
            hi = 0;
            int a3, b1, b2;
            for (e = head.right; e != head; e = e.right)
            {
                m = e.mk;
                a1 = First(m);
                m = (m - 1) & m;
                if (m == 0)
                    continue;
                a2 = First(m);
                if ((mm = (m - 1) & m) == 0)
                {
                    for (a3 = N2_1; a3 > a2; a3--)
                    {
                        if ((a = tb3[a1, a2, a3]) > (1 << 8))
                        {
                            b2 = (a & 0xff) - 1;
                            b1 = ((a >> 8) & 0xff) - 1;
                            if (b2 < b1)
                                throw new Exception();
                            m = ~(e.mk | list[b2].mk | list[b1].mk);
                            for (ee = head.right; ee.eid != b1; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                            for (ee = ee.right; ee.eid != b2; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                            for (ee = ee.right; ee != head; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                        }
                        else
                        {
                            tb3[a1, a2, a3] = (a << 8) | (e.eid + 1);
                            if (a == 0)
                            {
                                h1[hi] = a1;
                                h2[hi] = a2;
                                h3[hi] = a3;
                                hi++;
                            }
                        }
                    }
                    for (a2--; a2 > a1; a2--)
                    {
                        if ((a = tb3[a1, a2, a3]) > (1 << 8))
                        {
                            b2 = (a & 0xff) - 1;
                            b1 = ((a >> 8) & 0xff) - 1;
                            if (b2 < b1)
                                throw new Exception();
                            m = ~(e.mk | list[b2].mk | list[b1].mk);
                            for (ee = head.right; ee.eid != b1; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                            for (ee = ee.right; ee.eid != b2; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                            for (ee = ee.right; ee != head; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                        }
                        else
                        {
                            tb3[a1, a2, a3] = (a << 8) | (e.eid + 1);
                            if (a == 0)
                            {
                                h1[hi] = a1;
                                h2[hi] = a2;
                                h3[hi] = a3;
                                hi++;
                            }
                        }
                    }
                    for (a1--; a1 >= 0; a1--)
                    {
                        if ((a = tb3[a1, a2, a3]) > (1 << 8))
                        {
                            b2 = (a & 0xff) - 1;
                            b1 = ((a >> 8) & 0xff) - 1;
                            if (b2 < b1)
                                throw new Exception();
                            m = ~(e.mk | list[b2].mk | list[b1].mk);
                            for (ee = head.right; ee.eid != b1; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                            for (ee = ee.right; ee.eid != b2; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                            for (ee = ee.right; ee != head; ee = ee.right)
                                if (ee != e)
                                {
                                    changed |= ee.cell.mask(m);
                                    if (mk != mkb)
                                        goto Clear3i;
                                }
                        }
                        else
                        {
                            tb3[a1, a2, a3] = (a << 8) | (e.eid + 1);
                            if (a == 0)
                            {
                                h1[hi] = a1;
                                h2[hi] = a2;
                                h3[hi] = a3;
                                hi++;
                            }
                        }
                    }
                    continue;
                }
                a3 = First(mm);
                if (((mm - 1) & mm) == 0)
                {
                    if ((a = tb3[a1, a2, a3]) > (1 << 8))
                    {
                        b2 = (a & 0xff) - 1;
                        b1 = ((a >> 8) & 0xff) - 1;
                        if (b2 < b1)
                            throw new Exception();
                        m = ~(e.mk | list[b2].mk | list[b1].mk);
                        for (ee = head.right; ee.eid != b1; ee = ee.right)
                            if (ee != e)
                            {
                                changed |= ee.cell.mask(m);
                                if (mk != mkb)
                                    goto Clear3i;
                            }
                        for (ee = ee.right; ee.eid != b2; ee = ee.right)
                            if (ee != e)
                            {
                                changed |= ee.cell.mask(m);
                                if (mk != mkb)
                                    goto Clear3i;
                            }
                        for (ee = ee.right; ee != head; ee = ee.right)
                            if (ee != e)
                            {
                                changed |= ee.cell.mask(m);
                                if (mk != mkb)
                                    goto Clear3i;
                            }
                    }
                    else
                    {
                        tb3[a1, a2, a3] = (a << 8) | (e.eid + 1);
                        if (a == 0)
                        {
                            h1[hi] = a1;
                            h2[hi] = a2;
                            h3[hi] = a3;
                            hi++;
                        }
                    }
                }
            }
        Clear3i:
            while (--hi >= 0)
                tb3[h1[hi], h2[hi], h3[hi]] = 0;
            if (changed)
                goto Loop;
            #endregion
            #region 3x
            hi = 0;
            for (i = 0; i < N2; i++)
                if (ps[i] != 0)
                {
                    m = ps[i];
                    a1 = First(m);
                    m = (m - 1) & m;
                    if (m == 0)
                        continue;
                    a2 = First(m);
                    if ((mm = (m - 1) & m) == 0)
                    {
                        for (a3 = N2_1; a3 > a2; a3--)
                        {
                            if ((a = tb3[a1, a2, a3]) > (1 << 8))
                            {
                                m = (1LU << ((a & 0xff) - 1)) | (1LU << (((a >> 8) & 0xff) - 1)) | (1LU << i);
                                changed |= list[a1].cell.mask(m);
                                changed |= list[a2].cell.mask(m);
                                changed |= list[a3].cell.mask(m);
                            }
                            else
                            {
                                tb3[a1, a2, a3] = (a << 8) | (i + 1);
                                if (a == 0)
                                {
                                    h1[hi] = a1;
                                    h2[hi] = a2;
                                    h3[hi] = a3;
                                    hi++;
                                }
                            }
                        }
                        for (a2--; a2 > a1; a2--)
                        {
                            if ((a = tb3[a1, a2, a3]) > (1 << 8))
                            {
                                m = (1LU << ((a & 0xff) - 1)) | (1LU << (((a >> 8) & 0xff) - 1)) | (1LU << i);
                                changed |= list[a1].cell.mask(m);
                                changed |= list[a2].cell.mask(m);
                                changed |= list[a3].cell.mask(m);
                            }
                            else
                            {
                                tb3[a1, a2, a3] = (a << 8) | (i + 1);
                                if (a == 0)
                                {
                                    h1[hi] = a1;
                                    h2[hi] = a2;
                                    h3[hi] = a3;
                                    hi++;
                                }
                            }
                        }
                        for (a1--; a1 >= 0; a1--)
                        {
                            if ((a = tb3[a1, a2, a3]) > (1 << 8))
                            {
                                m = (1LU << ((a & 0xff) - 1)) | (1LU << (((a >> 8) & 0xff) - 1)) | (1LU << i);
                                changed |= list[a1].cell.mask(m);
                                changed |= list[a2].cell.mask(m);
                                changed |= list[a3].cell.mask(m);
                            }
                            else
                            {
                                tb3[a1, a2, a3] = (a << 8) | (i + 1);
                                if (a == 0)
                                {
                                    h1[hi] = a1;
                                    h2[hi] = a2;
                                    h3[hi] = a3;
                                    hi++;
                                }
                            }
                        }
                        continue;
                    }
                    a3 = First(mm);
                    if (((mm - 1) & mm) == 0)
                    {
                        if ((a = tb3[a1, a2, a3]) > (1 << 8))
                        {
                            m = (1LU << ((a & 0xff) - 1)) | (1LU << (((a >> 8) & 0xff) - 1)) | (1LU << i);
                            changed |= list[a1].cell.mask(m);
                            changed |= list[a2].cell.mask(m);
                            changed |= list[a3].cell.mask(m);
                        }
                        else
                        {
                            tb3[a1, a2, a3] = (a << 8) | (i + 1);
                            if (a == 0)
                            {
                                h1[hi] = a1;
                                h2[hi] = a2;
                                h3[hi] = a3;
                                hi++;
                            }
                        }
                    }
                }
            while (--hi >= 0)
                tb3[h1[hi], h2[hi], h3[hi]] = 0;
            if (changed)
                goto Loop;
            #endregion
            setsIQ.m[sid] = 0;
        }
    }
    class SetSync : Set
    {
        public SetSync(int sid)
            : base(sid) { }
        public override void get(int x)
        {
            lock(this)
                base.get(x);
        }
    }
    class IQ
    {
        public IQ(int n)
        {
            q = new int[n];
            m = new int[n];
            this.n = n;
        }
        int e = 0, i = 0, n;
        public virtual int Count { get { return this.i - this.e; } }
        public int[] m, q;
        public virtual int Next()
        {
            if (e == i)
                return -1;
            int ret = q[e % n];
            m[ret] = 0;
            e++;
            return ret;
        }
        public virtual int NextWait()
        {
            if (e == i)
                return -1;
            int ret = q[e % n];
            e++;
            return ret;
        }
        public virtual void Add(int a)
        {
            if (m[a] != 0)
                return;
            m[a] = 1;
            q[i % n] = a;
            i++;

        }
    }
    class IQsync:IQ
    {
        public IQsync(int n)
            : base(n)
        { }
        public override int Count
        {
            get
            {
                lock(this)
                    return base.Count;
            }
        }
        public override int Next()
        {
            lock(this)
                return base.Next();
        }
        public override int NextWait()
        {
            lock(this)
                return base.NextWait();
        }
        public override void Add(int a)
        {
            lock(this)
                base.Add(a);
        }
    }
    class ThreadRun
    {
        public ThreadRun()
        {
            tb = new int[N2, N2];
            for (int i = N2_1; i >= 0; i--)
                for (int j = N2_1; j >= 0; j--)
                    tb[i, j] = -1;
            tb3 = new int[N2, N2, N2];
            h1 = new int[N4];
            h2 = new int[N4];
            h3 = new int[N4];
            sms = new ulong[N2 + 1];
            new Thread(new ThreadStart(run)).Start();
        }
        public ulong[] sms;
        public int[,] tb;
        public int[, ,] tb3;
        public int[] h1, h2, h3;
        void run()
        {
            int curv;
        Loop:
            do
            {
                curv = version;
                int i;
                while ((i = setsIQ.NextWait()) >= 0)
                    sets[i].check(this);
                while ((i = subsIQ.Next()) >= 0)
                {
                    ulong m = 0LU;
                    foreach (int mid in subs[i])
                        m |= cells[mid].mk;
                    if (subsMask[i] != m)
                    {
                        subsMask[i] = m;
                        foreach (int pid in pairsOfSubs[i])
                            pairsIQ.Add(pid);
                    }
                }
                while ((i = pairsIQ.Next()) >= 0)
                {
                    ulong m = 0LU;
                    foreach (int sid in pairs[i])
                        m |= subsMask[sid];
                    if (pairsMask[i] != m)
                    {
                        pairsMask[i] = m;
                        pairsMask[i ^ 1] = m;
                        foreach (int sid in pairs[i ^ 1])
                            foreach (int mid in subs[sid])
                                if (rs[mid] == 0)
                                    cells[mid].mask(m);
                    }
                }
            } while (curv != version);
            Interlocked.Increment(ref waitings);
            while (curv == version && threading) ;
            if (curv != version && threading)
            {
                Interlocked.Decrement(ref waitings);
                goto Loop;
            }
        }
    }
    const int MTN = 2;
    static int waitings;
    static bool threading;
}
